COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0BASL30\M1BASI30\M2NGR40\M3BASB30\M4SUB\.
C00009 ENDMK
C⊗;
\\M0BASL30;\M1BASI30;\M2NGR40;\M3BASB30;\M4SUB;\.
\F2\CSTANFORD ARTIFICIAL INTELLIGENCE LABORATORY
\CDEPARTMENT OF COMPUTER SCIENCE
\CSTANFORD UNIVERSITY
\CSTANFORD, CALIFORNIA 94305
\F0





						

							August 23, 1974



Editor
\F1Communications of the ACM\F0
ACM Headquarters Office
1133 Avenue of the Americas
New York, New York 10036

Dear Sir:

\J	Friedman and Hoffman use an encipherment technique in their paper
\F1Execution Time Requirements for Encipherment Programs\F0 [\F1Communications of
the ACM\F0 17,8 (August 1974)] that seems grossly defective.  While they don't 
advertise it as good, someone might use it with regretable results.  The object of
this note is not just to point out the defect, but to pose the problem in general,
to make explicit an \F3strong adequacy\F0 criterion for ciphers, and to suggest a modification
of their system that apparently meets it.

	The method they use involves the generation of a pseudo random key as a sequence
{\F1x\F4n\F0} of numbers continued by the rule \F1x\F4n+1\F1 = ax\F4n\F1 + c (mod p)
\F0where \F1p\F0 is a prime.  The \F1x\F0's are then \F1exclusive-or\F0ed with packed words of 
the text to form the cryptogram.  In the case in question, the words are 60 bits long as fits
the CDC 6400.  The cipher is attacked as follows:

	The villain guesses a plain text sequence 240 bits long.  This may not always be
possible, and how he goes about it depends on what he already knows.  For example, he 
may know a favorite phrase, he may suspect a quotation, or the document may be a 
computer program containing a guessed subroutine or the user may be trying to keep
secret a modified version of a known program.

	The villain has a computer program that slides his 240 bits along the cryptogram
a character at a time and does an exclusive or in order to guess three successive 
\F1x\F4i\F0's totaling 180 bits--say \F1x\F4m\F1, x\F4m+1\F0, and \F1x\F4m+2\F0.
For each such guess, the program solves the linear equations \F1x\F4m+1\F1 = ax\F4m \F1+ c\F0
to get a conjectured \F1a\F0 and \F1c\F0.
The conjectured \F1a\F0 and \F1c\F0 are used to continue the sequence of \F1x\F4i\F0's,
i.e. to get \F1x\F4m+1\F0 and \F1x\F4m+4\F0.  These are \F1exclusive-or\F0ed with
more of the cryptogram to get further conjectured plain text.  The conjectured plain
text is tested with trigram tables to see if it is plausible English and any 
sequences passing the test are displayed to the villain at his console.  When he likes
what he sees, the search stops and prints the rest of the message.  This is the
probable word method well known in cryptography.

	The weakness of the cipher as described by Friedman and Hoffman is that the key sequence 
is continuable once 180 bits of it have been guessed.  The method can be improved
by subjecting the random output of the number generator to an information losing
transformation in order to get the running key.  Even using only every other
bit produced by the generator would make it unobvious how to proceed, but since the
villain's problem would still be linear, mathematics might save him.  A better idea
would be to use a second random number generator to select which bits from the 
output of the first generator would go into the key.  While this looks good to me, I don't certify 
it.

	All this suggests the following strong adequacy criterion for an encipherment system.  Suppose
all of the plain text known except for one character.  Then it should still require 
an unacceptable amount of work to learn more about the missing character than is 
suggested by the known remainder of the message.  In fact, let me suggest calling
such an encipherment system \F3strongly adequate\F0.

	Several years ago an encipherment system that we hoped was strongly adequate was installed as 
a utility program at the Stanford Artificial Intelligence Laboratory on our PDP-10.
Its fate is instructive.  A villain replaced the source program by one that whenever
used copied the name of the enciphered file and the starting keyword into a file in the system 
area.  This has subsequently been made more difficult, but perfect security has not been 
achieved.\.


   							Sincerely yours,



							John McCarthy
							Director, Artificial Intelligence Laboratory
							Professor of Computer Science